package _01_symmetricTree

/**
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3


Input:         root
              /    \
           p`        p
          / \       / \
         pl  pr    pl`  pr`
		/ \
	   ... 		   ...

对称树
依旧是利用分治法 参见100

我们站在p和p`上来看问题，如果该树是对称树，那么
1. 只有root结点，且没有左右子树
2. 有左右子树，且树为对称树

由此转化为判断两棵树是不是对称树

当p==null&&p`==null时，两树相等
当p或p`中只有一个为Null时，不相等
当p和p`都不为null且两节点相等时，只要p的左子树和p`的右子树对称且p的右子树和p`的左子树对称，则该树是对称树
*/

func main() {

}

func isSymmetric(root *TreeNode) bool {
	if root == nil {
		return true
	} else {
		return synmetricHelper(root.Left, root.Right)
	}
}

func synmetricHelper(p *TreeNode, q *TreeNode) bool {
	if p == nil && q == nil {
		return true
	} else if p == nil || q == nil {
		return false
	} else {
		return p.Val == q.Val && synmetricHelper(p.Left, q.Right) && synmetricHelper(p.Right, q.Left)
	}
}

func isSymmetric(root *TreeNode) bool {
	if root == nil {
		return true
	} else {
		return synmetricHelper(root.Left, root.Right)
	}
}

func synmetricHelper(left, right *TreeNode) bool {
	if left == nil && right == nil {
		return true
	} else if left == nil || right == nil {
		return false
	} else {
		return left.Val == right.Val && synmetricHelper(left.Left, right.Right) && synmetricHelper(left.Right, right.Left)
	}
}
